import random

def kcluster(Xmatrix, k, nodes):
    vlist = nodes
    vset = set(vlist)
    head = []
    head.append(vlist[0])
    b = []
    b.append(vset)
    for l in range(k - 1):
        h = -99999999
        v = -1
        rj = -1
        for j in range(l + 1):
            for vi in b[j]:
                if Xmatrix.has_key(head[j]) and Xmatrix[head[j]].has_key(vi):
                    if (Xmatrix[head[j]][vi] > h):
                        h = Xmatrix[head[j]][vi]
                        v = vi
                        rj = j
        if len(b) < l + 2:
            blist = []
            blist.append(v)
            bset = set(blist)
            b.append(bset)
        else:
            b[l + 1].add(v)
        b[rj].remove(v)
        head.append(v)
        unions = set([])
        for bs in b:
            unions = unions | bs
        for vt in unions:
            j = 0
            for bi in b:
                if vt in bi:
                    break
                j = j + 1
            cmp1 = 0
            cmp2 = 0
            if Xmatrix.has_key(vt) and Xmatrix[vt].has_key(v):
                cmp2 = Xmatrix[vt][v]
            if Xmatrix.has_key(vt) and Xmatrix[vt].has_key(head[j]):
                cmp1 = Xmatrix[vt][head[j]]
            if vt != head[j] and cmp1 > cmp2:
                b[j].remove(vt)
                b[l + 1].add(vt)
    #print b
    return b
def test(matrix, b, vlist):
    objfunc = 0.0
    for v1 in vlist:
        for v2 in vlist:
            if v1 == v2:
                continue
            j1 = -1
            j2 = -1
            j = 0
            for bi in b:
                if v1 in bi:
                    j1 = j
                if v2 in bi:
                    j2 = j
                j = j + 1
            if j1 == j2:
                continue
            if matrix.has_key(v1) and matrix[v1].has_key(v2):
                objfunc = objfunc + matrix[v1][v2]
            if matrix.has_key(v2) and matrix[v2].has_key(v1):
                objfunc = objfunc + matrix[v2][v1]
    print objfunc
#matrix = {5:{6:5, 7:5, 8:5, 9:1, 10:1, 12:1}, 6:{5:5, 10:1, 11:1, 7:10, 8:4}, 7:{5:5, 6:10, 8:40, 12:1}, 8:{5:5, 6:4, 7:40}, 9:{5:1, 10:100, 11:100, 12:100}, 10:{5:1, 9:100, 11:25, 6:1}, 11:{6:1, 9:100, 10:25, 12:90}, 12:{5:1, 7:1, 9:100, 11:90}}
#print matrix
#vlist = [5, 6, 7, 8, 9, 10, 11, 12]
#b =  kcluster(matrix, 3, vlist)
#print b
#objfunc = 0.0
#for v1 in vlist:
#    for v2 in vlist:
#        if v1 == v2:
#            continue
#        j1 = -1
#        j2 = -1
#        j = 0
#        for bi in b:
#            if v1 in bi:
#                j1 = j
#            if v2 in bi:
#                j2 = j
#            j = j + 1
#        if j1 == j2:
#            continue
#        if matrix.has_key(v1) and matrix[v1].has_key(v2):
#            objfunc = objfunc + matrix[v1][v2]
#        if matrix.has_key(v2) and matrix[v2].has_key(v1):
#            objfunc = objfunc + matrix[v2][v1]
#print objfunc
